class BinarySearchTree<T: Comparable<T>> {

    class Node<T>(var element: T) {
        var left: Node<T>? = null
        var right: Node<T>? = null
    }

    private var root: Node<T>? = null
    private var size: Int = 0

    fun getSize(): Int {
        return this.size
    }

    private fun isEmpty(): Boolean {
        return this.size == 0
    }

    // 外部调用的添加元素方法, 调用递归的添加元素方法
    fun add(element: T) {
        this.root = this.add(this.root, element)
    }

    // 递归添加元素方法
    private fun add(node: Node<T>?, element: T): Node<T> {
        if (node == null) {
            this.size += 1
            return Node(element)
        }

        if (element < node.element) {
            node.left = add(node.left, element)
        }else if (element > node.element) {
            node.right = add(node.right, element)
        }
        // 如果element = node.element 那么什么都不做

        return node
    }

    // 非递归方式添加元素
    fun circleAdd(element: T) {
        if (this.root == null) {
            this.size += 1
            this.root = Node(element)
        }else {
            var n = this.root!!
            while (n.element != element) {
                if (element < n.element) {
                    if (n.left == null) {
                    //
                        this.size += 1
                        n.left = Node(element)
                        break
                    }else {
                        n = n.left!!
                    }
                }else if (element > n.element) {
                    if (n.right == null) {
                        this.size += 1
                        n.right = Node(element)
                        break
                    }else {
                        n = n.right!!
                    }
                }
            }
        }
    }

    // 前序遍历
    fun preOrder() {
        this.preOrder(this.root)
    }

    // 前序遍历内部递归调用方法
    private fun preOrder(node: Node<T>?) {
        node?.let {
            print(it.element)
            this.preOrder(it.left)
            this.preOrder(it.right)
        }
    }

    // 中序遍历
    fun inOrder() {
        this.inOrder(this.root)
    }

    // 中序遍历内部递归调用方法
    private fun inOrder(node: Node<T>?) {
        node?.let {
            this.inOrder(it.left)
            print(it.element)
            this.inOrder(it.right)
        }
    }

    // 后序遍历
    fun postOrder() {
        this.postOrder(this.root)
    }

    // 后序遍历内部递归调用方法
    private fun postOrder(node: Node<T>?) {
        node?.let {
            this.postOrder(it.left)
            this.postOrder(it.right)
            print(it.element)
        }
    }

    // 前序遍历非递归方法
    fun preOrderNoRecursion() {
        // 利用链表栈实现
        val lls = LinkListStack<Node<T>>()

        this.root?.let {
            lls.push(it)
        }

        while (!lls.isEmpty()) {
            val node = lls.pop()
            node?.let {
                print(node.element)

                node.right?.let { right ->
                    lls.push(right)
                }
                node.left?.let { left ->
                    lls.push(left)
                }
            }
        }
    }

    // 层序遍历 通过链表队列实现
    fun levelOrder() {
        val llq = LinkListQueue<BinarySearchTree.Node<T>>()

        this.root?.let {
            llq.enqueue(it)
        }

        while (!llq.isEmpty()) {
            val node = llq.dequeue()
            node?.let {
                print(node.element)

                node.left?.let { left->
                    llq.enqueue(left)
                }
                node.right?.let { right ->
                    llq.enqueue(right)
                }
            }
        }
    }

    // 返回最小值
    fun miniElement(): T? {
        if (this.isEmpty()) {
            return null
        }
        return this.miniElement(this.root!!)
    }

    private fun miniElement(node: Node<T>): T {
        if (node.left == null) {
            return node.element
        }
        return this.miniElement(node.left!!)
    }

    // 返回最大值
    fun maxElement(): T? {
        if (this.isEmpty()) {
            return null
        }
        return this.maxElement(this.root!!)
    }

    private fun maxElement(node: Node<T>): T {
        if (node.right == null) {
            return node.element
        }
        return this.maxElement(node.right!!)
    }

    // 删除最小值
    fun deleteMiniNode(): T? {
        if (isEmpty()) {
            return null
        }

        val e = miniElement()
        this.root = this.deleteMiniNode(this.root!!)
        return e
    }

    private fun deleteMiniNode(node: Node<T>): Node<T>? {
        if (node.left == null) {
            val rightNode = node.right
            node.right = null
            this.size -= 1
            return rightNode
        }

        node.left = this.deleteMiniNode(node.left!!)
        return node
    }

    // 删除最大值
    fun deleteMaxNode(): T? {
        if (isEmpty()) {
            return null
        }

        val e = this.maxElement()
        this.root = this.deleteMaxNode(this.root!!)
        return e
    }

    private fun deleteMaxNode(node: Node<T>): Node<T>? {
        if (node.right == null) {
            val leftNode = node.left
            node.left = null
            this.size -= 1
            return leftNode
        }

        node.right = this.deleteMaxNode(node.right!!)
        return node
    }

    fun deleteElement(e: T) {
        if (isEmpty()) {
            return
        }

        this.root = this.deleteElement(e, this.root!!)
    }

    private fun deleteElement(e: T, node: Node<T>?): Node<T>? {
        if (node == null) {
            return null
        }

        if (e < node.element) {
            node.left = this.deleteElement(e, node.left)
            return node
        }else if (e > node.element) {
            node.right = this.deleteElement(e, node.right)
            return node
        }

        // 找到了e == node.element

        // 如果没有左子树
        if (node.left == null) {
            val rightNode = node.right
            node.right = null
            this.size -= 1
            return rightNode
        }

        // 如果没有右子树
        if (node.right == null) {
            val leftNode = node.left
            node.left = null
            this.size -= 1
            return leftNode
        }

        // 到这里了那肯定又有左子树，又有右子树
        // 选择当前结点的继任者结点, 就是右子树上最小结点
        val successor = Node<T>(this.miniElement(node.right!!))
        // 继结点的右结点绑定上当前结点的右结点去掉继任者
        successor.right = this.deleteMiniNode(node.right!!)
        // 继结点的左结点绑定上当前结点的左结点
        successor.left = node.left

        node.right = null
        node.left = null

        // 把successor返回给父节点替代当前node node就被删除了, 因为在removeMiniNode方法里有size -= 1所以不用专门写size -= 1
        return successor
    }
}